import java.util.*;
public class MaxFrequency {
    int maxFrequency(int[] nums, int k, int numOperations) {
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> diff = new TreeMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum); // cnt[x]++
            diff.putIfAbsent(x, 0); // 把 x 插入 diff，以保证下面能遍历到 x
            // 把 [x-k, x+k] 中的每个整数的出现次数都加一
            diff.merge(x - k, 1, Integer::sum); // diff[x-k]++
            diff.merge(x + k + 1, -1, Integer::sum); // diff[x+k+1]--
        }

        int ans = 0;
        int sumD = 0;
        for (Map.Entry<Integer, Integer> e : diff.entrySet()) {
            sumD += e.getValue();
            ans = Math.max(ans, Math.min(sumD, cnt.getOrDefault(e.getKey(), 0) + numOperations));
        }
        return ans;
    }


  
//     public int maxFrequency(int[] nums, int k, int numOperations) {
//         Arrays.sort(nums);

//         int n = nums.length;
//         int ans = 0;
//         int cnt = 0;
//         int left = 0;
//         int right = 0;
//         for (int i = 0; i < n; i++) {
//             int x = nums[i];
//             cnt++;
//             // 循环直到连续相同段的末尾，这样可以统计出 x 的出现次数
//             if (i < n - 1 && x == nums[i + 1]) {
//                 continue;
//             }
//             while (nums[left] < x - k) {
//                 left++;
//             }
//             while (right < n && nums[right] <= x + k) {
//                 right++;
//             }
//             ans = Math.max(ans, Math.min(right - left, cnt + numOperations));
//             cnt = 0;
//         }

//         if (ans >= numOperations) {
//             return ans;
//         }

//         left = 0;
//         for (right = 0; right < n; right++) {
//             int x = nums[right];
//             while (nums[left] < x - k * 2) {
//                 left++;
//             }
//             ans = Math.max(ans, right - left + 1);
//         }
//         return Math.min(ans, numOperations); // 最后和 numOperations 取最小值
//     }
// }
}






// 给你一个整数数组 nums 和两个整数 k 和 numOperations 。

// 你必须对 nums 执行 操作  numOperations 次。每次操作中，你可以：

// 选择一个下标 i ，它在之前的操作中 没有 被选择过。
// 将 nums[i] 增加范围 [-k, k] 中的一个整数。
// 在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

// 一个元素 x 的 频率 指的是它在数组中出现的次数。

 

// 示例 1：

// 输入：nums = [1,4,5], k = 1, numOperations = 2

// 输出：2

// 解释：

// 通过以下操作得到最高频率 2 ：

// 将 nums[1] 增加 0 ，nums 变为 [1, 4, 5] 。
// 将 nums[2] 增加 -1 ，nums 变为 [1, 4, 4] 。
// 示例 2：

// 输入：nums = [5,11,20,20], k = 5, numOperations = 1

// 输出：2

// 解释：

// 通过以下操作得到最高频率 2 ：

// 将 nums[1] 增加 0 。
 

// 提示：

// 1 <= nums.length <= 105
// 1 <= nums[i] <= 105
// 0 <= k <= 105
// 0 <= numOperations <= nums.length
